1. Field of the Invention
The present invention is directed to a system for improving the efficiency and quality of digital image compression systems that are used in printing and other image processing systems.
2. Description of the Related Art
Current laser beam printer engines found inside printers, copiers, fax machines, multifunctional equipment and other imaging systems are capable of printing high resolution image data at high speeds. For such a printer engine, the motion of the engine must be uninterrupted and a data stream must be provided to the engine at a high rate at precise timings (within a few nanoseconds) from the moment the printer engine picks up a sheet of paper (or a similar medium) and until the sheet is ejected with all the information properly printed on it. Since typical pixel data flows to the printer engine at a rate of tens of millions of pixels per second, there is very little time for on-the-fly computations.
One method for providing such a data stream to a printer engine requires complete preparation and storage of a full page of rasterized image data prior to commencing any printing. Such a method usually requires a large amount of memory.
Recently-introduced high-speed printers are capable of printing high-resolution images in multi-level grayscale or in multi-level color. In multi-level grayscale printing, for example, an 8-bit value is used to represent each pixel on a page. Accordingly, approximately 30,000,000 bytes of memory are required in order to store a full 8 xc2xdxe2x80x3 by 11xe2x80x3 8-bit grayscale image to be printed at 600 dots per inch (dpi). A multi-level color image of the same size and density requires four times as much memory, approximately 120,000,000 bytes, in order to store, for each pixel, 8-bit values corresponding to each of the cyan, magenta, yellow, and black components. For these images, a large amount of memory is needed if the image data for an entire page were rasterized prior to commencing printing. This incurs high costs that are commercially unacceptable in many markets.
In order to reduce the amount of memory required to store a page of image data to be printed and to maintain an uninterrupted stream of image data to a printer engine, a banding and compression technique has been suggested whereby the page is partitioned into parallel bands. Prior to printing, each band is rasterized using a rasterized band memory, compressed and stored in compressed form. The rasterized band memory is then released for re-use and subsequent bands are processed similarly. During printing, each processed band is decompressed back into rasterized image data xe2x80x9con the flyxe2x80x9d as the page is being printed.
The above technique requires: 1) A compression method which practically guarantees a minimum compression ratio, so as to be certain that a page of compressed image data bands will fit within a storage area of predesignated size, and 2) a decompression algorithm sufficiently fast to produce decompressed image data from the bands at the high rates required by laser beam printer engines.
Various compression techniques have been proposed to meet the above requirements. For example, lossless compression techniques such as Huffman, run-length, and Lempel-Ziv-Walsh (LZW) typically provide fast decompression, but these techniques cannot guarantee a particular compression ratio. Furthermore, although these techniques produce good compression ratios for binary images, such as text and black-only graphics images, lossless techniques often provide poor compression ratios when applied to multi-level images, particularly scanned color images.
In the event that lossless techniques fail to yield a required compression ratio, supplementary lossy compression techniques may be used.
JPEG compression, for example, can provide guaranteed minimum compression ratios, such as 10:1 or higher. However, image distortion due to JPEG processing tends to increase along with required compression ratios. If a required compression ratio is not too high (8:1 or less), image degradation is often unnoticeable for some multi-level images, such as natural photographs. However, JPEG compression blurs sharp edges, thereby significantly affecting the quality of text and graphics images.
Accordingly, what is needed is an improved lossless compression technique which provides acceptable (e.g., 4:1) compression ratios for a vast majority of possible input images and thereby reduces reliance on less-desirable lossy compression to a negligible minority of possible input images. Such an improved compression technique must also provide fast decompression so that print data is continuously provided to a printer engine during printing.
One improvement to lossless compression techniques is described in xe2x80x9cGraphics Gems IIxe2x80x9d, edited by James Arvo, pages 93 to 100, Academic Press Inc., 1991 (the xe2x80x9cHolt-Roberts Methodxe2x80x9d). The Holt-Roberts method is a two dimensional predictor-corrector technique which takes advantage of the similarity between neighboring pixels of high resolution images in order to convert the relatively flat statistics of an input image to statistics of differences (correctors), which are concentrated around zero and can therefore be compressed more effectively than the input image. Using the Holt-Roberts Method, an image is pre-processed by using a predictor algorithm to calculate a predictor value corresponding to each pixel of the image. For each predictor value, a corrector value is calculated based on the difference between the predictor value and its corresponding image pixel. The corrector values are stored in a corrector file which, in conjunction with the predictor algorithm, is completely descriptive or the original image file. The actual values of the predictor need not be stored. The corrector file is then subject to lossless compression.
If an effective predictor algorithm is used, many of the corrector values will be equal to zero or in the vicinity of zero. Advantageously, conventional lossless compression techniques such as Lempel-Ziv-Walsh or Huffman compression are most effective in achieving high compression ratios when compressing data having such an uneven statistical distribution. Accordingly, compression ratios achieved by applying lossless compression to the corrector obtained from predictor-corrector pre-processing of an image are significantly greater than those achieved by applying lossless compression directly to the original image.
However, while trying to realize the above method, Applicant encountered a problem inherent in practical implementations of predictor-corrector compression techniques. Applicant has discovered that implementation of Holt-Roberts usually results in a corrector file that is significantly larger then a corresponding original image file. The reason for this phenomenon is as follows. When applied to original image data having 8-bit pixel values ranging from 0 to 255, a predictor algorithm may, for example, produce predicted values also ranging from 0 to 255. Corresponding corrector values are calculated using the simple formula: corrector value =original image valuexe2x88x92predictor value. Accordingly, the range of possible corrector values is twice the range of the original image values, namely xe2x88x92255 to 255.
It should be noted the corrector may be positive or negative, so a sign bit is also required. As a result, whereas each original pixel value could be stored using one 8-bit sequence, storage of each corrector value in the above example requires up to ten bits. Other predictor algorithms may require even more bits per corrector value.
Most digital processing equipment is constructed to operate on data organized into 8-bit bytes. Therefore, in order to represent a corrector value requiring ten bits or more, it is generally contemplated to reserve two bytes of eight bits each. Such a corrector file can be twice as large as an original eight bits per pixel image file which it represents. As a result, any improvements in compression ratio due to the uneven statistical distribution of the corrector file will be diminished or eliminated by the expansion of the original file during pre-processing.
Accordingly, the conventional Holt-Roberts method does not provide both acceptable net compression ratios and fast decompression and delivery of print data to a printer engine.
The present invention addresses the foregoing problems by creating an intermingled corrector file including both corrector values and actual pixel values preceded by a special flag character. The pixel value/flag character pairs replace those corrector values that would require too many bits of storage memory, thus preserving the size of a corrector file storage memory at the cost of adding relatively few flag characters to a corrector file. As a result, if eight bits are required to represent actual image values, each value in the intermingled corrector file can be represented using eight bits as well. The intermingled corrector file is then compressed, thereby allowing the Holt-Roberts improvements in compression ratio to manifest themselves.
Thus, in one embodiment of the invention, raster image data including a number of pixels is pre-processed by calculating a predictor value of a target pixel, and by calculating a corrector value for the target pixel based on a difference between the predictor value of the pixel and on the pixel value. The corrector is stored in a memory in a case that: the corrector falls within a predetermined range. In a case that the corrector value falls outside the predetermined range, a flag character, followed by the pixel value of the target pixel, is stored in the memory. Finally, all data stored in the memory is compressed using a lossless compression technique.
By virtue of the foregoing arrangement, a predictor-corrector method of processing original image data prior to lossless compression can be implemented using a same bit-length group as that used to represent pixel values of the original image data, without creating a significant initial increase in the amount of data subsequently subjected to lossless compression. For example, Applicant has empirically measured initial inflation due to the insertion of flag characters on several images of various sources and contents and found that the inflation was less than 2% for computer-generated graphics and text, and less than 0.5% for scanned photographs. The overall compression ratio was better than 4:1 on almost all input images tested, and better than 8:1 on all computer-generated graphics and texts that were sampled.
According to a further aspect, it is determined whether to use lossless compression or to resort to lossy fall-back compression methods based on actual compression ratios achieved on a band-by-band basis. In particular, after a predetermined portion of a page has been processed, the compression ratio for the full page is predicted. The prediction can be based, for example, on the compression ratio of the portion of the page as well as other factors. If the predicted compression ratio is greater than a predetermined threshold, lossless processing continues. Otherwise, the lossless processing is abandoned and the page is processed using fall-back lossy compression.
Thus, in one embodiment of the invention, after approximately 25% of the page has been losslessly processed, the accumulated compression ratio is compared to a threshold of 3:1. If equal or greater, lossless processing continues until approximately 50% of the page is processed. At this point, an accumulated compression ratio of 3.5:1 or better is required in order to proceed. Another comparison is made at the 75% mark against a target compression ratio of 4:1. A final comparison is made near the end of the page to determine whether the processing and compression was completed successfully. If the compression fails due to lack of storage space or if the predicted compression ratio is lower than the threshold at any comparison point, lossless processing is abandoned and the page is re-processed using a lossy scheme (e.g., JPEG) with a guaranteed minimum compression ratio.
In a different embodiment, a predicted compression ratio is compared with a target ratio after each band has been processed.
Accordingly, the present invention provides a high quality (usually lossless) image compression and decompression subsystem for use in printing systems and other imaging applications.
This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiment thereof in connection with the attached drawings.